package xiaomin.demo.algorithm;

import java.util.Arrays;
/*
给定 两个 数组 表示 的 整数， 比如 x= 1234={ 1, 2, 3, 4}, y= 2410={ 2, 4, 1, 0}，
返回 第一个 整数 的 重组 后的 值 最接近 第二个 整数， 并且 大于 第二个 整数。
假设 两个 整数 的 数组 大小 相同， 并且 肯定 能 找出 符合 条件 的 数。
输入{ 1, 2, 3, 4} 和{ 2, 4, 1, 0}， 返回{ 2, 4, 1, 3}。

陈东锋. 进军硅谷:程序员面试揭秘 (技术移民参考手册) (pp. 73-74). 电子工业出版社. Kindle 版本.

思路：
1.对数组进行排序从小到大
2.构建一个数组used[]标记某一个数字是否已经被使用过
3.遍历数组,如果找到和它相等的数
    看下一个数是否可以找到比它大的,如果找不到,则需要选择下一个更大的数

 */
public class Lesson10 {
    public static void run(){
        int x[]={1,2,4,0};
        int y[]={2,4,1,0};

//        int x[]={1,2,4,0};
//        int y[]={2,4,1,0};
//        int x[]={1,2,5,0};
//        int y[]={2,4,1,0};
        int[] res=new int[x.length];

        //排序
        Arrays.sort(x);

        if(x[x.length-1]<y[0]){
            System.out.println("无法构建比y大的数");
            return;
        }

        int i=0,k=0;
        boolean equalsFlag=true;

        boolean used[] = new boolean[x.length];

        for(int j=0;j<x.length;j++){
            i=0;
            //从排序好的数字中选择等于或者大于的数
            while(i<x.length && (used[i] || x[i]<y[j])){
                i++;
            }
            //如果两个数字相等
            if(x[i]==y[j]){
                //判断下一个数字是否更小 24 23
                if(j<y.length-1 && x[x.length-1]<y[j+1]){
                    //大于
                    used[i+1]=true;
                    res[k++]=x[i+1];
                    //把剩余的复制过去
                    for(int m=0;m<x.length;m++){
                        if(!used[m]){
                            res[k++]=x[m];
                            used[m]=true;
                        }
                    }
                    break;
                }
                else {
                    used[i]=true;
                    res[k++]=x[i];
                }
            }
            else {
                used[i]=true;
                res[k++]=x[i];
                //把剩余的复制过去
                for(int m=0;m<x.length;m++){
                    if(!used[m]){
                        res[k++]=x[m];
                        used[m]=true;
                    }
                }
                break;
            }
        }
        for(int j=0;j<x.length;j++){
            System.out.println(res[j]);
        }

    }
}
